// https://leetcode.cn/problems/number-of-islands/description/

// 算法思路总结：
// 1. 广度优先搜索统计岛屿数量
// 2. 遍历网格，对未访问的陆地启动BFS
// 3. 使用方向数组进行四方向扩展
// 4. 全局vis数组配合memset重置状态
// 5. 边界检查确保不越界访问
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    typedef pair<int, int> PII;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int m, n;
    bool vis[301][301] = {false};

    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size(), n = grid[0].size();

        int ret = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (grid[i][j] == '1' && vis[i][j] == false)
                {
                    ret++;
                    bfs(i, j, grid);
                }
            }
        }
        return ret;
    }

    void bfs(int i, int j, vector<vector<char>>& grid)
    {
        queue<PII> q;
        q.push({i, j});
        vis[i][j] = true;

        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();

            for (int i = 0 ; i < 4 ; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x < m && x >= 0 && y < n && y >= 0 && vis[x][y] == false && grid[x][y] == '1')
                {
                    q.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
};

int main()
{
    vector<vector<char>> grid1 = {
        {'1','1','1','1','0'},
        {'1','1','0','1','0'},
        {'1','1','0','0','0'},
        {'0','0','0','0','0'}
    };
    
    vector<vector<char>> grid2 = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };

    Solution sol;

    cout << sol.numIslands(grid1) << endl;
    cout << sol.numIslands(grid2) << endl;
    

    return 0;
}
